// https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/

// 题干：给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
//       在 S 上反复执行重复项删除操作，直到无法继续删除。
//       在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

// 示例：输入："abbaca"
//       输出："ca"

// 碎语：栈的算法题难在看出来能不能用栈，看出来了就是模拟题

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    string removeDuplicates(string s)
    {
        // 利用栈的思想即可，不需要真的使用容器
        string res;

        for (int cur = 0 ; cur < s.size() ; cur++){
            if (res.empty()) res.push_back(s[cur]);
            else { // 栈不为空
                if (s[cur] == res.back()) res.pop_back();
                else res.push_back(s[cur]);
            }
        }

        return res;
    }
};

int main()
{
    Solution sol;
    string s = "abbaca";

    string index = sol.removeDuplicates(s);
    cout << index << endl;

    return 0;
}